home *** CD-ROM | disk | FTP | other *** search
/ Mac-Source 1994 July / Mac-Source_July_1994.iso / C and C++ / Libraries / stringsearch / bmsource / lC.fwdg.md2.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-05-06  |  3.6 KB  |  171 lines  |  [TEXT/MPS ]
  1. /*
  2.     search routine generated by gen.
  3.     skip=lC, match=fwd, guard=guard, shift=md2
  4. */
  5. #include    "freq.h"
  6. #include    "sd.h"
  7. /*
  8.  * The authors of this software are Andrew Hume and Daniel Sunday.
  9.  * 
  10.  * Copyright (c) 1991 by AT&T and Daniel Sunday.
  11.  * 
  12.  * Permission to use, copy, modify, and distribute this software for any
  13.  * purpose without fee is hereby granted, provided that this entire notice
  14.  * is included in all copies of any software which is or includes a copy
  15.  * or modification of this software and in all copies of the supporting
  16.  * documentation for such software.
  17.  * 
  18.  * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED
  19.  * WARRANTY.  IN PARTICULAR, NEITHER THE AUTHORS NOR AT&T MAKE ANY
  20.  * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY
  21.  * OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.
  22.  */
  23.  
  24. #ifndef    CHARTYPE
  25. #define    CHARTYPE    unsigned char
  26. #endif
  27. #define    MAXPAT    256
  28.  
  29. #define    TABTYPE    unsigned char
  30. #include    "stats.h"
  31.  
  32. #ifndef    TABTYPE
  33. #define    TABTYPE    long
  34. #endif
  35. typedef TABTYPE Tab;
  36.  
  37. static struct
  38. {
  39.     int patlen;
  40.     CHARTYPE pat[MAXPAT];
  41.     Tab delta[256];
  42.     int loopoffset;    /* patlen-1 - skip loop char */
  43.     int rarec, rareoff;
  44.     int md2;
  45. } pat;
  46.  
  47. prep(base, m)
  48.     CHARTYPE *base;
  49.     register m;
  50. {
  51.     CHARTYPE *skipc;
  52.     register CHARTYPE *pe, *pb;
  53.     register int j, r;
  54.     register Tab *d;
  55.     double tmax, fr;
  56.     extern double tcmp;
  57.     extern option;
  58.     int rrr, rr;
  59.     register CHARTYPE *pmd2;
  60.  
  61.     pat.patlen = m;
  62.     if(m > MAXPAT)
  63.         abort();
  64.     memcpy(pat.pat, base, m);
  65.     skipc = 0;
  66.     stats.len = m;
  67.     if(sd[m] == 0){
  68.         for(j = m; sd[j] == 0; j--)
  69.             sd[j] = 12;
  70.     }
  71.     d = pat.delta;
  72.     tmax = 2+tcmp;
  73.     for(pb = pat.pat, pe = pb+pat.patlen-1; pb <= pe; pb++){
  74.         fr = (1+tcmp*freq[*pb])/sd[pb-pat.pat];
  75. #ifdef    STATS
  76. /*printf("i=%d: f=%.4f freq[%c]=%.5f sd=%.1f\n", (pb-pat.pat), fr, *pb, freq[*pb], sd[pb-pat.pat]);/**/
  77. #endif
  78.         if(tmax > fr){
  79.             tmax = fr;
  80.             r = pb-pat.pat;
  81.         }
  82.     }
  83.     pat.loopoffset = m-1-r;
  84. if(option >= 0) pat.loopoffset=option;
  85.     skipc = &pat.pat[m-1-pat.loopoffset];
  86.     for(j = 0; j < 256; j++)
  87.         d[j] = m-pat.loopoffset;
  88.     for(pb = pat.pat, pe = pb+m-1-pat.loopoffset; pb <= pe; pb++){
  89.         d[*pb] = pe-pb;
  90.     }
  91.     rrr = 0;
  92.     for(rr = 1; rr < m; rr++){
  93.         if(freq[pat.pat[rr]] < freq[pat.pat[rrr]])
  94.             rrr = rr;
  95.     }
  96.     pat.rarec = pat.pat[rrr];
  97.     pat.rareoff = rrr;
  98.     for(pmd2 = skipc-1; pmd2 >= pat.pat; pmd2--)
  99.         if (*pmd2 == *skipc) break;
  100.     pat.md2 = skipc - pmd2;    /* *pmd2 is first leftward reoccurance of *pe */
  101. #ifdef    STATS
  102.     stats.extra += pat.md2;
  103. #endif
  104. }
  105.  
  106. exec(base, n)
  107.     CHARTYPE *base;
  108. {
  109.     int nmatch = 0;
  110.     register CHARTYPE *e, *s;
  111.     register Tab *d0 = pat.delta;
  112.     register k, s_offset;
  113.     register ro, rc;
  114.     register CHARTYPE *p, *q;
  115.     register CHARTYPE *ep;
  116.     register md2 = pat.md2;
  117.  
  118.     k = pat.patlen-1-pat.loopoffset;    /* k is char we loop on */
  119.     s = base+k;
  120.     e = base+n;
  121.     memset(e, pat.pat[k], pat.patlen);
  122.     s_offset = -k;
  123.     ro = pat.rareoff+s_offset;
  124.     rc = pat.rarec;
  125.     ep = pat.pat + pat.patlen;
  126.     while(s < e){
  127. #ifdef    STATS
  128.         k = d0[*s];
  129.         stats.jump++;
  130.         while(k){
  131.             stats.jump++; stats.step[k]++;
  132.             k = d0[*(s += k)];
  133.             stats.jump++; stats.step[k]++;
  134.             k = d0[*(s += k)];
  135.             stats.jump++; stats.step[k]++;
  136.             k = d0[*(s += k)];
  137.         }
  138.         if(s >= e)
  139.             return(nmatch);
  140. #else
  141.         k = d0[*s];
  142.         while(k){
  143.             k = d0[*(s += k)];
  144.             k = d0[*(s += k)];
  145.             k = d0[*(s += k)];
  146.         }
  147.         if(s >= e)
  148.             return(nmatch);
  149. #endif
  150. #ifdef    STATS
  151.         stats.slow++;
  152. #endif
  153.         if(s[ro] != rc)
  154.             goto mismatch;
  155.         for(p = pat.pat, q = s+s_offset; p < ep; ){
  156. #ifdef    STATS
  157.             stats.cmp++;
  158. #endif
  159.             if(*q++ != *p++)
  160.                 goto mismatch;
  161.         }
  162.         nmatch++;
  163.     mismatch:
  164. #ifdef    STATS
  165.         stats.step[md2]++; stats.jump++;
  166. #endif
  167.         s += md2;
  168.     }
  169.     return(nmatch);
  170. }
  171.